#pragma once
#include<vector>
#include<functional>
#include<algorithm>
namespace mypriority_queue
{
    template <class T, class Container = std::vector<T>, class Compare = std::less<T> >
    class priority_queue
    {
    public:
        priority_queue()
            :_c(Container())
        {}
        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            //Container tmp(first, last);
            //make_heap(tmp.begin(), tmp.end(),_comp);
            //_c = tmp;
            InputIterator it = first;
            while (it != last)
            {
                push(*it);
                it++;
            }
        }
        bool empty() const
        {
            return _c.empty();
        }
        size_t size() const
        {
            return _c.size();
        }
        const T& top() const
        {
            return _c.front();
        }
        T& top()
        {
            return _c.front();
        }
        void adjustDown()
        {
            size_t parent = 0;
            while (parent < _c.size())
            {
                size_t child = parent * 2 + 1;
                if (child < _c.size() - 1 && _comp(_c[child], _c[child + 1]))
                {
                    child++;
                }
                if (child < _c.size() && _comp(_c[parent], _c[child]))
                {
                    std::swap(_c[parent], _c[child]);
                    parent = child;
                }
                else
                {
                    break;
                }
            }
        }
        void adjustUp()
        {
            size_t child = _c.size() - 1;
            while (child)
            {
                size_t parent = (child - 1) / 2;
                if (_comp(_c[parent], _c[child]))
                {
                    std::swap(_c[parent], _c[child]);
                    child = parent;
                }
                else
                {
                    break;
                }
            }
        }
        void push(const T& x)
        {
            _c.push_back(x);
            adjustUp();
            //make_heap(_c.begin(), _c.end(), _comp);
        }
        void pop()
        {
            std::swap(_c[0], _c[_c.size() - 1]);
            _c.pop_back();
            adjustDown();
            //make_heap(_c.begin(), _c.end(), _comp);
            
        }
    private:
        Container _c;
        Compare _comp;
    };

};